/*
 * @lc app=leetcode.cn id=139 lang=java
 *
 * [139] 单词拆分
 */

// @lc code=start
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //单词可以重复使用，单词作为物品，字符串作为背包=>判断物品是否可以装满背包，顺序也有关系
        //外层遍历背包，内层遍历物品
        boolean[] dp=new boolean[s.length()+1];
        dp[0]=true;
        for(int i=0;i<=s.length();i++){
            for(String word:wordDict){
                int len=word.length();
                if(i>=len&&dp[i-len]&&word.equals(s.substring(i-len,i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
// @lc code=end

